//https://leetcode.cn/problems/string-compression-ii/submissions/589257186/
class Solution {
public:
    int memo[101][101];

    int getDigitSize(int count) {
        if (count >= 100) {
            return 3;
        }
        else if (count >= 10) {
            return 2;
        }
        else if (count > 1) {
            return 1;
        }
        return 0;
    }

    int getLengthOfOptimalCompressionUtil(string& s, int k, int start) {
        int n = (int)s.size();
        if (start == n) {
            return 0;
        }

        int& val = memo[start][k];
        if (val != -1) {
            return val;
        }
        int ans = INT_MAX;

        //keep
        for (int i = start, same = 0, del = 0; i < n; i++) {
            if (s[i] == s[start]) {
                same++;
            }
            else {
                del++;
            }
            if (k < del) break;
            int inc = 1 + getDigitSize(same);
            ans = min(ans, inc + getLengthOfOptimalCompressionUtil(s, k - del, i + 1));
        }
        //delete
        if (k > 0)
            ans = min(ans, getLengthOfOptimalCompressionUtil(s, k - 1, start + 1));
        return val = ans;
    }


    int getLengthOfOptimalCompression(string s, int k) {
        memset(memo, -1, sizeof(memo));
        return getLengthOfOptimalCompressionUtil(s, k, 0);
    }

};
